import java.util.ArrayList;
import java.util.Collections;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 29
 * Time: 17:48
 */
//牛客 二叉搜索树的最近公共祖先
public class Solution2 {
    //法一 根据官方思路自己写的代码    在线路上从后到前比较两个路径，直到找到第一个相同的点为止，第一个相同的节点就是最近公共祖先
    public static int lowestCommonAncestor (TreeNode root, int p, int q) {
        ArrayList<TreeNode> arrayList1 = new ArrayList<>();
        ArrayList<TreeNode> arrayList2 = new ArrayList<>();
        TreeNode root1 = root;
        TreeNode root2 = root;
        while (root1.val != p) {
            if(root1.val < p) {
                arrayList1.add(root1);
                root1 = root1.right;
            }else if(root1.val > p) {
                arrayList1.add(root1);
                root1 = root1.left;
            }
        }
        arrayList1.add(root1);
        while (root2.val != q) {
            if(root2.val < q) {
                arrayList2.add(root2);
                root2 = root2.right;
            }else if(root2.val > q) {
                arrayList2.add(root2);
                root2 = root2.left;
            }
        }
        arrayList2.add(root2);
        Collections.reverse(arrayList1);
        Collections.reverse(arrayList2);
        for (int i = 0; i < arrayList1.size(); i++) {
            for (int j = 0; j < arrayList2.size(); j++) {
                if(arrayList1.get(i) == arrayList2.get(j)) {
                    return arrayList1.get(i).val;
                }
            }
        }
        return -1;
    }

    //法二 官方推荐方法    在线路上从前到后比较两个路径，直到找到第一个不同的点为止，最后一个相同的节点就是最近公共祖先
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        //节点值都不同，可以直接用值比较
        while(node.val != target){
            path.add(node.val);
            //小的在左子树
            if(target < node.val)
                node = node.left;
                //大的在右子树
            else
                node = node.right;
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor1 (TreeNode root, int p, int q) {
        //求根节点到两个节点的路径
        ArrayList<Integer> path_p = getPath(root, p);
        ArrayList<Integer> path_q = getPath(root, q);
        int res = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < Math.min(path_p.size(), path_q.size()); i++){
            int x = path_p.get(i);
            int y = path_q.get(i);
            //最后一个相同的节点就是最近公共祖先
            if(x == y)
                res = path_p.get(i);
            else
                break;
        }
        return res;
    }
}
